import com.sun.xml.internal.txw2.output.DumpSerializer;

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

class MyStack {
    public Queue<Integer> Queue1= new LinkedList<>();
    public Queue<Integer> Queue2= new LinkedList<>();
    public MyStack() {

    }

    public void push(int x) {
        Queue1.offer(x);
        while(Queue1.size()>1){
            Queue2.offer(Queue1.poll());
        }

    }

    public int pop() {
        if(Queue1.isEmpty()){
            while(Queue2.size()>1){
                Queue1.offer(Queue2.poll());
            }
            int tmp=Queue2.poll();
            while(Queue1.size()>0){
                Queue2.offer(Queue1.poll());
            }
            return tmp;
        }else{
            return Queue1.poll();
        }
    }

    public int top() {
        if(Queue1.isEmpty()){
            while(Queue2.size()>1){
                Queue1.offer(Queue2.poll());
            }
            int tmp=Queue2.poll();
            while(Queue1.size()>0){
                Queue2.offer(Queue1.poll());
            }
            Queue2.offer(tmp);
            return tmp;
        }else{
            return Queue1.peek();
        }
    }

    public boolean empty() {
        return Queue1.isEmpty() && Queue2.isEmpty();
    }
}
class MyCircularQueue {
     public int[] list;
     public int usedsize;
     public int front=0;
     public int rear=0;
     public int length=0;
    public MyCircularQueue(int k) {
         this.list=new int[k+1];
         this.length=k+1;
    }

    public boolean enQueue(int value) {
        if(isFull()) return false;
        list[rear]=value;
        rear=(rear+1)%length;
        usedsize++;
        return true;
    }

    public boolean deQueue() {
      if(isEmpty()) return false;
        front=(front+1)%length;
        usedsize--;
        return true;
    }

    public int Front() {
        if(isEmpty()) return -1;
        return list[front];
    }

    public int Rear() {
        if(isEmpty()) return -1;
        if(rear==0) return list[length-1];
        else return list[rear-1];
    }

    public boolean isEmpty() {
     if(usedsize==0) return true;
     else return false;
    }

    public boolean isFull() {
    if((rear+1)%length==front) return true;
    else return false;
    }
}
class Solution1 {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (!s.equals("*") && !s.equals("+") && !s.equals("-") && !s.equals("/")) {
                int tmp = Integer.parseInt(s);
                stack.push(tmp);
            } else {
                int nums2 = stack.pop();
                int nums1 = stack.pop();
                switch (s) {
                    case "+":
                        stack.push(nums1 + nums2);
                        break;
                    case "-":
                        stack.push(nums1 - nums2);
                        break;
                    case "*":
                        stack.push(nums1 * nums2);
                        break;
                    case "/":
                        stack.push(nums1 / nums2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
         int i=0;
         int j=0;
        for(;i<pushA.length;i++){
            stack.push(pushA[i]);
            while(!stack.empty() && stack.peek()== popA[j]){
                stack.pop();
                 j++;
            }
        }
        return stack.empty();
    }
}
//括号匹配问题
//class Solution {
//    public boolean isValid(String s) {
//        Stack<Character> stack=new Stack<>();
//        for(int i=0;i<s.length();i++){
//            if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{')
//            {
//                stack.push(s.charAt(i));
//            }else{
//                if(stack.empty()) return false;
//                char tmp=stack.pop();
//                if(s.charAt(i)==')' && tmp=='(' || s.charAt(i)=='}' && tmp=='{' || s.charAt(i)==']' && tmp=='[' ) continue;
//                else return false;
//            }
//        }
//        if(stack.empty()) return true;
//        else return false;
//    }
//}

//括号匹配问题

//3.栈的弹出压入序列难
//import java.util.*;
//        import java.util.ArrayList;
//
//public class Solution {
//    public  boolean IsPopOrder(int[] pushA, int[] popA) {
//        Stack<Integer> stack = new Stack<>();
//        int i=0;
//        int j=0;
//        for(;i<pushA.length;i++){
//            stack.push(pushA[i]);
//            while(!stack.empty() && stack.peek()== popA[j]){
//                stack.pop();
//                j++;
//            }
//        }
//        return stack.empty();
//    }
//}
//3.栈的弹出压入序列

//4.逆波兰表达式求值
//class Solution {
//    public static int evalRPN(String[] tokens) {
//        Stack<Integer> stack=new Stack<>();
//        for(int i=0;i<tokens.length;i++){
//            String s=tokens[i];
//            if(!s.equals("*") && !s.equals("+") && !s.equals("-") && !s.equals("/") ){
//                int tmp=Integer.parseInt(s);
//                stack.push(tmp);
//            }else{
//                int nums2=stack.pop();
//                int nums1=stack.pop();
//                switch(s){
//                    case "+":
//                        stack.push(nums1+nums2);
//                        break;
//                    case "-":
//                        stack.push(nums1-nums2);
//                        break;
//                    case "*":
//                        stack.push(nums1*nums2);
//                        break;
//                    case "/":
//                        stack.push(nums1/nums2);
//                        break;
//                }
//            }
//        }
//        return stack.pop();
//    }
//}

//4.逆波兰表达式求值



//删除链表中所有值为value的元素
//class Solution {
//    public ListNode removeElements(ListNode head, int val) {
//        ListNode cur=head;
//        ListNode prev=null;
//        while(cur!=null){
//            if(cur.val==val) {
//                if(prev==null){
//                    head=head.next;
//                    prev=null;
//                }else{
//                    prev.next=cur.next;
//                }
//                cur=cur.next;
//                continue;
//            }
//            prev=cur;
//            cur=cur.next;
//        }
//        return head;
//    }
//}
//删除链表中所有值为value的元素

//单链表的逆置
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head==null) return null;
//        ListNode cur=head;
//        ListNode prev=null;
//        ListNode next=head;
//        while(cur!=null)
//        {
//            next=cur.next;
//            cur.next=prev;
//            prev=cur;
//            cur=next;
//        }
//        return prev;
//    }
//}
//单链表的逆置

//获取链表的中间节点
//class Solution {
//    public ListNode middleNode(ListNode head) {
//        ListNode fast=head;
//        ListNode slow=head;
//        while(fast!=null && fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        return slow;
//    }
//}
//获取链表的中间节点

//获取链表倒数第K个节点
//public class Solution {
//    public ListNode FindKthToTail(ListNode  head,int k) {
//        if(head==null || k<=0) return null;
//        ListNode fast=head;
//        ListNode slow=head;
//        int flag=1;
//        while(fast.next!=null){
//            fast=fast.next;
//            if(flag>=k) slow=slow.next;
//            flag++;
//        }
//        if(flag<k) return null;
//        return slow;
//    }
//}
//获取链表倒数第K个节点
